package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class fourteen3 {
    public static List<Integer> findAnagrams(String s, String p) {
        int m=s.length();
        int n=p.length();
        List<Integer> list=new ArrayList<>();
        if(m<n){
            return list;
        }
        HashMap<Character,Integer> HashMap=new HashMap<>();
        HashMap<Character,Integer> HashMap1=new HashMap<>();
        for(int i=0;i<n;i++){
            char in=p.charAt(i);
            HashMap.put(in,HashMap.getOrDefault(in,0)+1);
        }
        int left=0;
        int right=0;
        for(left=0,right=0;right<m;right++){
            char in1=s.charAt(right);
            HashMap1.put(in1,HashMap1.getOrDefault(in1,0)+1);
            if(right==left+n-1){
                if(HashMap.equals(HashMap1)){
                    list.add(left);
                }
                char out=s.charAt(left);
                HashMap1.put(out,HashMap1.get(out)-1);
                if(HashMap1.get(out)==0){
                    HashMap1.remove(out);
                }
                left++;
            }
        }
        return list;

    }
    public static void main(String[] args) {
//        s = "cbaebabacd", p = "abc"
        String s="cbaebabacd";
        String p="abc";
        List<Integer> anagrams = findAnagrams(s, p);
        System.out.println(anagrams);
    }
}
